GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Downhill-Simplex-Verfahren</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Downhill-Simplex-Verfahren</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Das Downhill-Simplex-Verfahren oder Nelder-Mead-Verfahren<a href="#cite_note-1">[1]</a> ist im Unterschied zum Namensvetter für lineare Probleme (<a href="Simplex-Algorithmus" class="mw-redirect" title="Simplex-Algorithmus">Simplex-Algorithmus</a>) eine Methode zur <a href="Optimierungsverfahren" class="mw-redirect" title="Optimierungsverfahren">Optimierung</a> <a href="Nichtlinear" class="mw-redirect" title="Nichtlinear">nichtlinearer</a> <a href="Funktion_(Mathematik)" title="Funktion (Mathematik)">Funktionen</a> von mehreren <a href="Parameter_(Mathematik)" title="Parameter (Mathematik)">Parametern</a>. Er fällt in die Kategorie der <a href="Bergsteigeralgorithmus" title="Bergsteigeralgorithmus">Hillclimbing</a>- oder Downhill-<a href="Suchverfahren" title="Suchverfahren">Suchverfahren</a>. Angewendet werden kann er z. B. auch beim <a href="Ausgleichungsrechnung" title="Ausgleichungsrechnung">Kurvenfitten</a>.

Es wurde von <a href="John_Nelder" title="John Nelder">John Nelder</a> und <a href="Roger_Mead" title="Roger Mead">Roger Mead</a> 1965 eingeführt.

<div class="mw-heading mw-heading2"><h2 id="Grundlagen">Grundlagen</h2></div>

Als Besonderheit kommt dieser Simplex-Algorithmus ohne <a href="Differentialrechnung" title="Differentialrechnung">Ableitungen</a> der Funktion nach den Parametern aus, welche bei manchen Problemstellungen nicht mit vertretbarem Aufwand berechenbar sind. Durch sinnvolle Vergleiche der Funktionswerte mehrerer Punkte im Parameterraum wird ähnlich wie bei einer <a href="Regula_falsi" title="Regula falsi">Regula falsi</a> mit <a href="Schrittweitensteuerung" title="Schrittweitensteuerung">Schrittweitensteuerung</a> die Tendenz der Werte und der <a href="Gradient_(Mathematik)" title="Gradient (Mathematik)">Gradient</a> Richtung Optimum angenähert. Das Verfahren <a href="Konvergenz_(Mathematik)" title="Konvergenz (Mathematik)">konvergiert</a> nicht extrem schnell, ist aber dafür einfach und relativ robust.

Der <a href="Algorithmus" title="Algorithmus">Algorithmus</a> basiert auf einem <a href="Simplex_(Mathematik)" title="Simplex (Mathematik)">Simplex</a>, dem einfachsten <a href="Volumen" title="Volumen">Volumen</a> im <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">-dimensionalen Parameterraum, das aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fdf2b9cbfe9051fd4e7b50c8028866d497eac35b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.066ex; height:2.343ex;" alt="{\displaystyle N+1}" loading="lazy"> Punkten aufgespannt wird. Im Eindimensionalen auf der <a href="Zahlengerade" title="Zahlengerade">Zahlengeraden</a> ist das eine <a href="Strecke_(Geometrie)" title="Strecke (Geometrie)">Strecke</a>, im Zweidimensionalen ein <a href="Dreieck" title="Dreieck">Dreieck</a> usw. Jeder Punkt entspricht dabei einem (Koordinaten-)Satz Parameter (bzw. Variablen), und zu jedem Punkt kann man einen Funktionswert berechnen, den man z. B. als Fehler- oder Kostenwert ansehen kann. Unter diesen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fdf2b9cbfe9051fd4e7b50c8028866d497eac35b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.066ex; height:2.343ex;" alt="{\displaystyle N+1}" loading="lazy"> Punkten ermittelt man dann den „schlechtesten“ und den „besten“. Von einem <a href="Iteration" title="Iteration">Iterationsschritt</a> zum nächsten wird normalerweise der „schlechteste“ dieser Punkte durch einen neuen ersetzt, der hoffentlich „besser“ ist. Den „besten“ Punkt behält man als bisher beste Lösung immer bei.

Bei einer Visualisierung im Zweidimensionalen mit Höhenlinien für die zu optimierende Funktion sieht man (in den Bildern rechts) ein Dreieck, das sich zielstrebig dem Optimum nähert, indem es sich um eine seiner Seiten klappt, sich streckt oder in der Nähe des Optimums um dieses zusammenzieht. Siehe auch die Abbildung ganz unten.

Ohne Ableitungen entfallen diverse Fallen wie pathologisches Verhalten dieser Ableitungen bei <a href="Unstetigkeit" class="mw-redirect" title="Unstetigkeit">Unstetigkeiten</a>, sodass das Verfahren zwar im Allgemeinen langsamer <a href="Konvergenzgeschwindigkeit" title="Konvergenzgeschwindigkeit">konvergiert</a> (nämlich linear) als Optimierungsverfahren mit Ableitungen, aber wesentlich robuster arbeitet. Die möglichen Fallen beim Simplex-Verfahren sind ähnlich wie bei den meisten Optimierungsverfahren unverhoffte lokale Nebenminima (bzw. -maxima), auf die konvergiert werden kann, oder dass das Verfahren sich für einen oder mehrere Parameter zu früh auf einen konstanten Wert zusammenzieht.

<div class="mw-heading mw-heading2"><h2 id="Algorithmus">Algorithmus</h2></div>

Das Downhill-Simplex-Verfahren findet ein lokales Optimum einer Funktion mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> Variablen (Parametern). Gegeben ist eine Zielfunktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\mathbb {R} ^{N}\rightarrow \mathbb {R} }">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\mathbb {R} ^{N}\rightarrow \mathbb {R} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5b151052d986c176784229e0e8b543cd40f5a81b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.877ex; height:3.009ex;" alt="{\displaystyle f:\mathbb {R} ^{N}\rightarrow \mathbb {R} }" loading="lazy">, die jedem Punkt im Lösungsraum einen Wert (Qualität der Lösung) zuordnet. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha ,\gamma ,\beta ,\sigma \in \mathbb {R} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha ,\gamma ,\beta ,\sigma \in \mathbb {R} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/579734a00754148ffbc655985c5e31e642d9039e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.032ex; height:2.676ex;" alt="{\displaystyle \alpha ,\gamma ,\beta ,\sigma \in \mathbb {R} }" loading="lazy"> sind Parameter des Algorithmus.

<ol><li>wähle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fdf2b9cbfe9051fd4e7b50c8028866d497eac35b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.066ex; height:2.343ex;" alt="{\displaystyle N+1}" loading="lazy"> Anfangspunkte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0},x_{1},\cdots ,x_{N}\in \mathbb {R} ^{N}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0},x_{1},\cdots ,x_{N}\in \mathbb {R} ^{N}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/758cf42c971116b753962c14801744806ede4608.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.211ex; height:3.009ex;" alt="{\displaystyle x_{0},x_{1},\cdots ,x_{N}\in \mathbb {R} ^{N}}" loading="lazy">, die den Simplex bilden</li>

<li>sortiere die Punkte nach dem Wert der Zielfunktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/132e57acb643253e7810ee9702d9581f159a1c61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" loading="lazy">, so dass <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86f21d0e31751534cd6584264ecf864a6aa792cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{0}}" loading="lazy"> der beste, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{N-1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{N-1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7df9ede29e0429afc8d9b7d32c831ab2df6723e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.122ex; height:2.009ex;" alt="{\displaystyle x_{N-1}}" loading="lazy"> der zweitschlechteste und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{N}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{N}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/03fe4fcca886b79103468f2dbef6a0c8332b746d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.021ex; height:2.009ex;" alt="{\displaystyle x_{N}}" loading="lazy"> der schlechteste ist</li>

<li>bilde von allen außer dem schlechtesten Punkt den Mittelpunkt: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m={\frac {1}{N}}\sum \nolimits _{i=0}^{N-1}x_{i}}">

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m={\frac {1}{N}}\sum \nolimits _{i=0}^{N-1}x_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a2cd89dcb6c80e44cb2c0d3d69e9e1cbaa0ab7f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:18.089ex; height:5.176ex;" alt="{\displaystyle m={\frac {1}{N}}\sum \nolimits _{i=0}^{N-1}x_{i}}" loading="lazy"></li>

<li>reflektiere den schlechtesten Punkt am Mittelpunkt: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r=m+\alpha (m-x_{N})}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r=m+\alpha (m-x_{N})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1d6f85a60c03726f04a53a397fa06f451535e0b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.227ex; height:2.843ex;" alt="{\displaystyle r=m+\alpha (m-x_{N})}" loading="lazy"></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> besser ist als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86f21d0e31751534cd6584264ecf864a6aa792cf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{0}}" loading="lazy">: bestimme den expandierten Punkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e=r+\gamma (r-m)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e=r+\gamma (r-m)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2062af7a06768f55bb2b57185f5867119c3648f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.072ex; height:2.843ex;" alt="{\displaystyle e=r+\gamma (r-m)}" loading="lazy">, ersetze <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{N}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{N}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/03fe4fcca886b79103468f2dbef6a0c8332b746d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.021ex; height:2.009ex;" alt="{\displaystyle x_{N}}" loading="lazy"> durch den besseren der beiden Punkte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e,r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e,r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/823931ee70e8da13600b5643f10625e53e402a4f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.166ex; height:2.009ex;" alt="{\displaystyle e,r}" loading="lazy"> und gehe zu Schritt 2</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> besser ist als der zweitschlechteste Punkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{N-1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{N-1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7df9ede29e0429afc8d9b7d32c831ab2df6723e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.122ex; height:2.009ex;" alt="{\displaystyle x_{N-1}}" loading="lazy">: ersetze <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{N}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{N}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/03fe4fcca886b79103468f2dbef6a0c8332b746d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.021ex; height:2.009ex;" alt="{\displaystyle x_{N}}" loading="lazy"> durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> und gehe zu Schritt 2</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"> der bessere der beiden Punkte <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{N},r}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{N},r}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e33248f221cb1f9b2b6c52a32bb2cc78c271d7ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.104ex; height:2.009ex;" alt="{\displaystyle x_{N},r}" loading="lazy">. Bestimme den kontrahierten Punkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c=h+\beta (m-h)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c=h+\beta (m-h)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b0db80c26b9dfd418985a172693cfa48f4305943.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.646ex; height:2.843ex;" alt="{\displaystyle c=h+\beta (m-h)}" loading="lazy"></li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> besser ist als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{N}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{N}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/03fe4fcca886b79103468f2dbef6a0c8332b746d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.021ex; height:2.009ex;" alt="{\displaystyle x_{N}}" loading="lazy">: ersetze <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{N}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{N}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/03fe4fcca886b79103468f2dbef6a0c8332b746d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.021ex; height:2.009ex;" alt="{\displaystyle x_{N}}" loading="lazy"> durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"> und gehe zu Schritt 2</li>

<li>komprimiere den Simplex: für jedes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i\in \{1,\cdots ,N\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i\in \{1,\cdots ,N\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6e90dcc5cef9152da0413d9179c27de26b79eeb1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.372ex; height:2.843ex;" alt="{\displaystyle i\in \{1,\cdots ,N\}}" loading="lazy">: ersetze <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}+\sigma (x_{0}-x_{i})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}+\sigma (x_{0}-x_{i})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0f70dcb733cc69af855210a85f71952ac28dec6c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.462ex; height:2.843ex;" alt="{\displaystyle x_{i}+\sigma (x_{0}-x_{i})}" loading="lazy"></li>

<li>gehe zu Schritt 2</li></ol>

Nach diesen Regeln wird die Iteration so lange weitergeführt, bis ein Konvergenzkriterium erfüllt ist. Der Simplex wird sich dabei in Richtung eines lokalen Optimums verlagern und sich schließlich um dieses herum zusammenziehen.

<th>Parameter</th>

<th>sinnvoller Bereich</th>

<th>typischer Wert

</th></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b79333175c8b3f0840bfb4ec41b8072c83ea88d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.488ex; height:1.676ex;" alt="{\displaystyle \alpha }" loading="lazy"> (Reflexion)</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha >0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/edd4f784b6e8bb68fa774213ceacbab2d97825dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.749ex; height:2.176ex;" alt="{\displaystyle \alpha >0}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \alpha =1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/03d67a45a44be8b8f15e99b7def2b0cf0aba1717.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.749ex; height:2.176ex;" alt="{\displaystyle \alpha =1}" loading="lazy">

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a223c880b0ce3da8f64ee33c4f0010beee400b1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.262ex; height:2.176ex;" alt="{\displaystyle \gamma }" loading="lazy"> (Expansion)</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma >0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/775a6435e4270cddf2cd7dcb486c20f7f4bb8cee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.523ex; height:2.676ex;" alt="{\displaystyle \gamma >0}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma =1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5682ebb86d6f024a15f4a2c1c7cb08412720bcaf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.523ex; height:2.676ex;" alt="{\displaystyle \gamma =1}" loading="lazy">

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7ed48a5e36207156fb792fa79d29925d2f7901e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.332ex; height:2.509ex;" alt="{\displaystyle \beta }" loading="lazy"> (Kontraktion)</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0<\beta <1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5823463cddbbeea88e7e3a68c879cc6f391f7e4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.854ex; height:2.509ex;" alt="{\displaystyle 0<\beta <1}" loading="lazy"></td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta =0{,}5}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0b4e4dc0da0338f8481eceadad64c0629c3f0d15.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.402ex; height:2.509ex;" alt="{\displaystyle \beta =0{,}5}" loading="lazy">

</td></tr>

<tr>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/59f59b7c3e6fdb1d0365a494b81fb9a696138c36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle \sigma }" loading="lazy"> (Komprimierung)</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0<\sigma <1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/033763281d338863d62ad91904482fefb149dee4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.852ex; height:2.176ex;" alt="{\displaystyle 0<\sigma <1}" loading="lazy"></td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sigma =0{,}5}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe37a7f68104aeccffd0a6efde893e0d928712a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.4ex; height:2.509ex;" alt="{\displaystyle \sigma =0{,}5}" loading="lazy">

</td></tr></tbody></table>

Die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fdf2b9cbfe9051fd4e7b50c8028866d497eac35b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.066ex; height:2.343ex;" alt="{\displaystyle N+1}" loading="lazy"> Anfangspunkte müssen so gewählt werden, dass sie einen Simplex der Dimension <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> aufspannen und nicht alle in einer <a href="Hyperebene" title="Hyperebene">Hyperebene</a> von kleinerer Dimension liegen, d. h. die Vektoren <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}-x_{0},x_{2}-x_{0},...,x_{N}-x_{0}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}-x_{0},x_{2}-x_{0},...,x_{N}-x_{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b1ef1b6dec32d1f301bef6b329445c68c543c8bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:29.666ex; height:2.343ex;" alt="{\displaystyle x_{1}-x_{0},x_{2}-x_{0},...,x_{N}-x_{0}}" loading="lazy"> müssen <a href="Lineare_Unabh%C3%A4ngigkeit" title="Lineare Unabhängigkeit">linear unabhängig</a> sein. Man kann z. B. einen Punkt als Startpunkt wählen und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> weitere ermitteln, indem man von diesem aus jeweils einen der Parameter um einen von 1 verschiedenen Faktor (falls der Parameter nicht 0 sein kann) oder einen von 0 verschiedenen Summanden erhöht. Alternativ: Man gibt für jeden Parameter zwei verschiedene Werte vor, berechnet den ersten Punkt mit allen Erstwerten und die anderen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> Punkte auch mit den Erstwerten, nur dass jeweils einer der Parameter durch seinen Zweitwert ersetzt wird.

Oder man wählt <a href="Zufallszahlengenerator" title="Zufallszahlengenerator">Zufallspunkte</a> aus dem Lösungsraum.

<div class="mw-heading mw-heading2"><h2 id="Grafische_Darstellung_eines_Beispiellaufs">Grafische Darstellung eines Beispiellaufs</h2></div>

Das Bild zeigt das Ergebnis eines Programmlaufs. Die roten und blauen Linien stellen die Gefällelinien für Täler bzw. Berge dar. Es handelt sich um einen Kreisgraben in einer schrägen Ebene, es interessiert hier das lokale Minimum innerhalb des Kreisgrabens. Die Simplex-Iteration findet das Minimum an der Kreuzungsstelle der roten Linien. In <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">- und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">-Richtung reicht die Grafik von 0 bis 4.

<div class="mw-heading mw-heading2"><h2 id="Erweiterungen_für_Notfälle">Erweiterungen für Notfälle</h2></div>

Wie bei anderen Verfahren besteht immer die Gefahr, dass auf ein Nebenoptimum konvergiert wird.

Diese Gefahr kann man durch mehrere Maßnahmen mindern:

<ul><li>Nach einer bestimmten Anzahl von Schritten wird neu angesetzt. Dazu wird der bisher beste Punkt beibehalten und um ihn herum ein neuer Start-Simplex aufgebaut, indem bei jedem weiteren Punkt die Koordinate (nur) eines Parameters z. B. um 5 % variiert wird.</li>

<li>Genau wie eben, nur werden die zusätzlichen Simplex-Punkte durch Zufallswerte noch mehr flexibilisiert.</li>

<li>Statt solche Maßnahmen nach einer festen Anzahl von Schritten zu ergreifen, kann man den Zeitpunkt auch vom aktuellen Stand der Iteration abhängig machen. Dazu muss das Problem natürlich besser bekannt sein, dass man sich dessen auch sicher sein kann.</li>

<li>Alternativ kann man sogar den Zeitpunkt der Neuansetzung per Zufallszahl variabel gestalten.</li>

<li>Eine zusätzliche Sicherheitsabfrage könnte den Fall abfangen, dass sich nur einer der Parameter vorzeitig festgelaufen hat, dann könnte man ihm eine Spezialbehandlung zukommen lassen.</li></ul>

All diese Varianten erfordern eine intensive Beschäftigung mit dem jeweiligen konkreten Problem, es gibt leider keine allgemein gültigen Kochrezepte dafür.

<div class="mw-heading mw-heading2"><h2 id="Erweiterung_zum_Kurvenfitten">Erweiterung zum Kurvenfitten</h2></div>

Will man nicht eine einzelne <a href="Analytische_Funktion" title="Analytische Funktion">analytische Funktion</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> Parametern (Koordinaten) optimieren,

sondern eine Theoriefunktion an eine Messkurve anpassen, ist nur ein kleiner zusätzlicher Schritt notwendig:

Als zu optimierende Funktion verwendet man oft die Fehlerquadratsumme, also die Summe aus den Quadraten der Differenzen aus den einzelnen Messwerten (Kurvenpunkten) und den Theoriefunktionswerten an denselben Stellen, wobei letztere einerseits von der <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">-Koordinate der Messkurve abhängen und zusätzlich von den <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> Parametern. Ob man aus der Fehlerquadratsumme noch die Wurzel zieht, ist für das Simplex-Verfahren irrelevant. Siehe hierzu auch <a href="Methode_der_kleinsten_Quadrate" title="Methode der kleinsten Quadrate">Methode der kleinsten Quadrate</a>.

Jedoch ist das Downhill-Simplex-Verfahren sehr flexibel (anders als etwa der <a href="Levenberg-Marquardt-Algorithmus" title="Levenberg-Marquardt-Algorithmus">Levenberg-Marquardt-Algorithmus</a>), man kann also je nach Situation auch andere Funktionen zur Optimierung verwenden:

<ul><li>Die Daten haben eine starke Streuung: Statt der Summe der quadrierten Abweichung minimiert man die Summe der <a href="Betragsfunktion" title="Betragsfunktion">Beträge</a> der Abweichungen. <a href="Ausrei%C3%9Fer" title="Ausreißer">Ausreißer</a> beeinflussen das Ergebnis weniger.</li>

<li>Kurvenanpassung arbeitet normalerweise mit der Annahme, dass der Fehler der abhängigen Variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\Delta y=y_{calc}-y_{obs})}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (\Delta y=y_{calc}-y_{obs})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dbd81eaa4b79d86c7ae6720d83601e0165b7afe0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.64ex; height:2.843ex;" alt="{\displaystyle (\Delta y=y_{calc}-y_{obs})}" loading="lazy"> unabhängig von der zugehörigen unabhängigen Variable ist (<a href="Homoskedastizit%C3%A4t" class="mw-redirect" title="Homoskedastizität">Homoskedastizität</a>). In manchen Fällen ist jedoch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7caae142d915be8ef4d8c423bf91d1f6ea10e8e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.091ex; height:2.509ex;" alt="{\displaystyle \Delta y}" loading="lazy"> eine Funktion von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy">. Diese Situation tritt insbesondere dann auf, wenn sich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> über mehrere Größenordnungen erstrecken. Würde man in solchen Fällen die Fehlerquadratsumme minimieren, bekäme man eine gute Anpassung bei großen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x/y}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x/y}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c9f79732fa39115855a4cf9b64d2a63971a41046.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.648ex; height:2.843ex;" alt="{\displaystyle x/y}" loading="lazy">-Werten, aber eine sehr schlechte bei kleinen, die zur Fehlerquadratsumme kaum beitragen. In solchen Fällen minimiert man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \chi ^{2}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \chi ^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8c0cc9237ec72a1da6d18bc8e7fb24cdda43a49a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.509ex; height:3.009ex;" alt="{\displaystyle \chi ^{2}}" loading="lazy">, also die Summe der quadrierten relativen Abweichungen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Sigma (\Delta y/y)^{2}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Sigma (\Delta y/y)^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4522c602682c659b355b8fe1ef8393194437a961.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.951ex; height:3.176ex;" alt="{\displaystyle \Sigma (\Delta y/y)^{2}}" loading="lazy">.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Beispielimplementierung">Beispielimplementierung</h2></div>

<a href="Pseudocode" title="Pseudocode">Pseudocode</a> (<a href="C_(Programmiersprache)" title="C (Programmiersprache)">C-ähnlich</a>):

<pre>// Deklarationen

</pre>

<pre>// Benutzervorgaben, -eingaben

int NP= ... ; // Anzahl der Parameter, die in FQS() eingehen,

// auch "Dimension des Parameterraums"

</pre>

<pre>double ParP[NP]={ ... }; // primärer Parametersatz

double ParS[NP]={ ... }; // sekundärer Parametersatz, gibt Schwankungsbreite vor

</pre>

<pre>double FQS(int pf) // Zu minimierende Funktion, hängt

{ // von den Parametern Par0[pf][...] ab.

... // Muss je nach Problemstellung erstellt werden.

// So schreiben, dass sie für den Parametersatz Nr. pf

} // berechnet und am Schluss in Par0[pf][0] (s. u.)

// abgespeichert wird.

</pre>

<pre>// Ende Benutzervorgaben

</pre>

<pre>// Initialisierung

</pre>

<pre>// Simplex-Parameter

double NA = 1, NB = .5, NC = 2; // Alpha, Beta, Gamma

</pre>

<pre>// Parametersätze, NP+1 Stück für den Simplex selbst, plus 3 weitere

double Par0[NP+4][NP+1];

// darin 1. Index: 0..NP die (NP+1) Parametersätze des Simplex,

// dabei auf 0 immer der schlechteste Punkt des Simplex,

// auf 1 immer der beste Punkt des Simplex

// NP+1 Punkt P*, s. u.

// NP+2 Punkt P**, s. u.

// NP+3 Mittelpunkt P-Quer des Simplex, s. u.

// darin 2. Index: 0 Fehlerwert für diesen Satz

// 1..NP einzelne Parameterwerte dieses Satzes

</pre>

<pre>// Initialisierung

</pre>

<pre>// Simplex aus Primär- und Sekundärwerten

Parametersätze 0 bis NP mit Primärwerten belegen;

In Parametersätzen 1 bis NP (i) jeweils

Parameter Nr. i mit Sekundärwert belegen;

</pre>

<pre>// Berechnung der Anfangs-Fehlersummen

für Parametersätze 0 bis NP: feh=FQS(i); // speichert Ergebnis in Par0[i][0], s. o.

</pre>

<pre>// Schleife für Iteration, Hauptschleife

bool fertig = false;

while (!fertig)

NT++; // Simplex-Schritt Nr. NT

</pre>

<pre> // schlechtesten und besten Punkt ermitteln (höchster bzw. niedrigster Fehlerwert)

Werte fmin und fmax auf Fehlerwert von Satz Nr. 0 vorbelegen;

für alle Parametersätze von 1 bis NP:

wenn Fehler für Satz Nr. i größer als fmax:

noch schlechterer Punkt, fmax auf diesen Wert, Punkt mit Nr. 0 tauschen

wenn Fehler für Satz Nr. i kleiner als fmin:

noch besserer Punkt, fmin auf diesen Wert, Punkt mit Nr. 1 tauschen

</pre>

<pre> // Konvergenzabfrage, sind wir fertig?

// Dies muss auch je nach Problem individuell erstellt werden,

// hier als Beispiel die Bedingung, dass alle Parameter nur noch um 1 ‰

// schwanken.

</pre>

<pre> fertig = true;

für alle Parameter in allen Parametersätzen von 0 bis NP:

wenn nur für einen Parameter die relative Abweichung des Wertes

zwischen schlechtestem und bestem Punkt größer als 0.001, dann:

fertig=false; // doch noch nicht fertig

</pre>

<pre> //Wenn fertig, dann beende mit bestem Punkt Par0[1][1..3] als Ergebnis des Algorithmus

</pre>

<pre> // Mittelpunkt P-QUER des Simplex nach Index NP+3

Mittelwerte über Sätze 1 bis NP (also ohne schlechtesten Punkt Nr. 0!) bilden

und als Satz Nr. NP+3 speichern;

</pre>

<pre> // Punkt P* durch Reflexion des schlechtesten Punkts

// am Mittelpunkt P-QUER (mit Nelder/Mead-Parameter alpha=NA) nach Index NP+1

innerhalb eines Parametersatzes:

Par0[NP+1][i]=(1 + NA) * Par0[NP+3][i] - NA * Par0[0][i];

fs=Par0[NP+1][0]=FQS(NP+1); // und Fehler berechnen

</pre>

<pre> // Fallunterscheidung, ob Verbesserung erreicht

wenn fs<fmin // neuer Punkt P* im Vergleich zu bisher bestem

/ // ja, besser!

| // weiteren Schritt zu Punkt P** in dieselbe Richtung nach Index NP+2

| // (mit Nelder/Mead-Parameter gamma=NC)

| innerhalb eines Parametersatzes:

| Par0[NP+2][i]=(1 + NC) * Par0[NP+1][i] - NC * Par0[NP+3][i];

| fs=Par0[NP+2][0]=FQS(NP+2); // und Fehler berechnen

|

| wenn fs>=fmin // wieder Vergleich mit bisher bestem Punkt

| / // keine weitere Verbesserung: P** verwerfen, P* nach Index 0,

| | // also bisher schlechtesten Wert durch neuen (etwas besseren) ersetzen

| \ Parametersatz Nr. NP+1 nach Nr. 0 kopieren;

| else // von fs>=fmin

| / // ja, auch eine Verbesserung!

| | // auch besser als P* ?

| | wenn fs>Par0[NP+1][0]

| | / // nein, P* weiterverwenden und damit bisher schlechtesten auf Index 0 ersetzen

| | \ Parametersatz Nr. NP+1 nach Nr. 0 kopieren;

| | else // von fs>Par0[NP+1][0]

| | / // ja, P** weiterverwenden und damit bisher schlechtesten auf Index 0 ersetzen

\ \ \ Parametersatz Nr. NP+2 nach Nr. 0 kopieren;

</pre>

<pre> else // von fs<fmin

/ // nicht besser als bisher bester, nun prüfen, ob P* wenigstens überhaupt eine Verbesserung

| wenn fs von P* für wenigstens einen der Punkte 2..NP kleiner ist, dann:

| / // ja, besser als mindestens einer, mit P* den bisher schlechtesten Punkt auf Index 0 ersetzen

| \ Parametersatz Nr. NP+1 nach Nr. 0 kopieren;

| else // von fs von P*

| / // nein, weiterhin schlechter als die anderen Punkte

| | // Zusatzprüfung: sogar schlechter als bisher schlechtester Punkt fmax?

| | wenn fs>fmax // schlechter als bisher schlechtester?

| | // ja, erstmal nichts tun

| | else // von fs>fmax

| | / // nein, also wenigstens bisher schlechtesten Punkt damit ersetzen

| \ \ Parametersatz Nr. NP+1 nach Nr. 0 kopieren;

| // neuer Punkt P** durch Kontraktion zwischen bisher schlechtestem Punkt (Index 0)

| // und P-QUER (Index NP+3) nach Index NP+2 (mit Nelder/Mead-Parameter beta=NB)

| innerhalb eines Parametersatzes:

| Par0[NP+2][i]= NB * Par0[0][i] + (1 - NB) * Par0[NP+3][i];

| fs=Par0[NP+2][0]=FQS(NP+2); // und Fehler berechnen

| // P** besser als bisher schlechtester Punkt?

| wenn fs<fmax // besser als bisher schlechtester?

| / // ja, bisher schlechtesten durch P** ersetzen

| \ Parametersatz Nr. NP+2 nach Nr. 0 kopieren;

| else // von fs<fmax

| / // nein, keinerlei Verbesserung, Notfall

| | // folgt allgemeine Kompression um Faktor 2 um den bisher besten Punkt herum

| | für alle Parametersätze außer Nr. 1 (bisher bester): // also j=0 und 2..NP

| | innerhalb eines Parametersatzes j:

| | Par0[j][i]=(Par0[j][i] + Par0[1][i]) / 2;

\ \ fs=Par0[j][0]=FQS(j); // und Fehler berechnen

// Schleifenende

</pre>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>John Ashworth Nelder, Roger Mead: A Simplex Method for Function Minimization. Computer Journal, 1965, 7, 308–313 (<a rel="nofollow" class="external text" href="http://comjnl.oxfordjournals.org/cgi/reprint/7/4/308.pdf">Originaltext als PDF-Datei</a>, 543 kB)</li>

<li>William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery: <a href="Numerical_Recipes" title="Numerical Recipes">Numerical Recipes</a> in C. Foundation Books 2007, ISBN 978-81-85618-16-6.</li>

<li>Jeffrey C. Lagarias, James A. Reeds, Margaret H. Wright, Paul E. Wright: <cite style="font-style:italic">Convergence Properties of the Nelder-Mead Simplex Method in Low Dimensions</cite>. In: <cite style="font-style:italic">SIAM Journal on Optimization</cite>. Band 9, Nr. 1, 1998, S. 112–147, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137/S1052623496303470">10.1137/S1052623496303470</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Downhill-Simplex-Verfahren&rft.atitle=Convergence+Properties+of+the+Nelder-Mead+Simplex+Method+in+Low+Dimensions&rft.au=Jeffrey+C.+Lagarias%2C+James+A.+Reeds%2C+Margaret+H.+Wright%2C+...&rft.date=1998&rft.doi=10.1137%2FS1052623496303470&rft.genre=journal&rft.issue=1&rft.jtitle=SIAM+Journal+on+Optimization&rft.pages=112-147&rft.volume=9" style="display:none"> </li>

<li>Larry Nazareth, Paul Tseng: <a rel="nofollow" class="external text" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.41.9788&rep=rep1&type=pdf">Gilding the Lily: A variant of the Nelder-Mead algorithm based on Golden-Section Search</a>. Computational Optimization and Applications, Bd. 22 (2002), Nr. 1, S. 133–144</li>

<li>Saša Singer, Sanja Singer: <a rel="nofollow" class="external text" href="http://onlinelibrary.wiley.com/doi/10.1002/anac.200410015/abstract">Efficient implementation of the Nelder-Mead search algorithm.</a> Applied Numerical Analysis and Computational Mathematics, Bd. 1 (2004), Nr. 2, S. 524–534 (Zusammenfassung)</li>

<li>Marco A. Luersen, Rodolphe Le Riche: <a rel="nofollow" class="external text" href="https://www.emse.fr/~leriche/gbnm_cas.pdf">Globalized Nelder–Mead method for engineering optimization.</a> Computers and Structures 82 (2004), S. 2251–2260</li>

<li>Andrej Prša, Tomaž Zwitter: <a rel="nofollow" class="external text" href="http://adsabs.harvard.edu/full/2005ESASP.576..611P">Introducing adapted Nelder & Mead's downhill simplex method to a fully automated analysis of eclipsing binaries.</a> In: C. Turon, K. S. O’Flaherty, M. A. C. Perryman (Hrsg.): The Three-Dimensional Universe with Gaia (ESA SP-576). Proc. Gaia Sympos. 2004, ESA Publications Division, Nordwijk 2005, S. 611–614</li>

<li>David Byatt, Ian Coope, Chris Price: <a rel="nofollow" class="external text" href="http://oldweb.cecm.sfu.ca/AAS/coope.pdf">40 years of the Nelder-Mead algorithm</a> (PDF-Datei; 3,46 MB)</li>

<li>Fuchang Gao, Lixing Han: <a rel="nofollow" class="external text" href="http://www.webpages.uidaho.edu/~fuchang/res/anms.pdf">Implementing the Nelder-Mead simplex algorithm with adaptive parameters.</a> Computational Optimization and Applications 51 (2012), Nr. 1, S. 259–277</li>

<li>Jeffrey C. Lagarias, Bjorn Poonen, Margaret H. Wright: <a rel="nofollow" class="external text" href="http://arxiv.org/abs/1104.0350">Convergence of the restricted Nelder-Mead algorithm in two dimensions.</a> SIAM J. Optimization 22 (2012), Nr. 2, S. 501–532</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> J. A. Nelder, R. Mead: <cite style="font-style:italic">A Simplex Method for Function Minimization</cite>. In: <cite style="font-style:italic">The Computer Journal</cite>. Band 7, Nr. 4, 1. Januar 1965, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%220010-4620%22&key=cql">0010-4620</a>, S. 308–313, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093/comjnl%2F7.4.308">10.1093/comjnl/7.4.308</a>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Downhill-Simplex-Verfahren&rft.atitle=A+Simplex+Method+for+Function+Minimization&rft.au=J.+A.+Nelder%2C+R.+Mead&rft.date=1965-01-01&rft.doi=10.1093%2Fcomjnl%2F7.4.308&rft.genre=journal&rft.issn=0010-4620&rft.issue=4&rft.jtitle=The+Computer+Journal&rft.pages=308-313&rft.volume=7" style="display:none">

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-07-14" href="https://de.wikipedia.org/wiki/?title=Downhill-Simplex-Verfahren&oldid=257894579">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>